#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        vector<int> dp;
        dp.push_back(nums[0]);
        for(int i = 1;i<nums.size();++i){
            dp.push_back(max(nums[i],dp[i-1]+nums[i]));
        }
        return *max_element(dp.begin(),dp.end());
    }
};


int main(){
    Solution S;
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    cout<<S.maxSubArray(nums)<<endl;
}